import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description: 最大公约数
 * User: DELL
 * Date: 2024-05-24
 * Time: 9:02
 */
public class Main4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-- > 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            int d = scanner.nextInt();
            int k = scanner.nextInt();
            a = fun(a, k);
            b /= k;
            c = fun(c, k);
            d /= k;
            int ans = 0;
            for (int i = a; i <= b; i++) {
                for (int j = c; j <= d; j++) {
                    if (gcd(i, j) == 1) {
                        ans++;
                    }
                }
            }
            System.out.println(ans);
        }
    }

    private static int fun(int n, int k) {
        if (n % k == 0) {
            return n / k;
        } else {
            return n / k + 1;
        }
    }

    private static int gcd(int a, int b) {
        if (a % b != 0) {
            return gcd(b, a % b);
        }
        return b;
    }
}
